/*
 * Maximum Path Sum II Solution.
 */

package Graph;

import java.util.Iterator;

/**
 * Implementation of a graph using adjacency list representation.<br />
 * Based on material in the CLRS text.  The current implementation is not fully 
 * realized and thus there are a number of restrictions:
 * <br />
 * 
 *  (1) The graph cannot be resized after it is created. <br />
 *  (2) The graph must be a directed graph. <br />
 *
 * 
 * @author Michael Silva
 */

public class AdjacencyListGraph implements Graph {
    
    /**
     * Static nested class that defines a graph edge for use in an adjacency
     * list.  Each <code>Edge</code> is associated with a <code>Vertex</code>
     * in the adjacency list.
     */
    public static class Edge
    {
        /** Adjacent vertex. */
        public Vertex vert;
        
        /** Pointer to next edge. */
        public Edge successor;
        
        /**
         * Instantiate a new <code>Edge</code>.  
         * 
         * @param vert The adjacent vertex.
         * @param successor The next edge
         */
        public Edge (Vertex vert, Edge successor)
        {
            this.vert = vert;
            this.successor = successor;
        }
    }
    
    
    /**
     * Class to represents a vertex, its incident edges, and its 
     * adjacent vertices.
     */
    protected static class AdjListEntry
    {
        /** Vertex whose incident edges will be listed. */
        public Vertex thisVertex;
        
        /** Pointer to the head of the edges list. */
        public Edge head;
        
        /**
         * Create a new <code>AdjListEntry</code> object.  
         * 
         * @param v Vertex to be added to the adjacency list.
         */
        public AdjListEntry (Vertex v)
        {
            thisVertex = v;
            head = null;
        }
    }
    
    
    /**
     * Class for iterating through a list of <code>Edge</code> objects.<br />  
     * Note: Current implementation provides direct access to objects
     * in the underlying list.  This should be changed to instead provide
     * copies by using either a copy constructor or an implementation of 
     * <code>Object.clone()</code>.
     */
    public class EdgeIterator implements Iterator
    {
        /** Index of the vertex the <code>EdgeIterator</code> is associated
            with */
        private int vIndex;
        
        /** Current edge pointed to by the iterator. */
        private Edge current;
        
        /**
         * Create a new iterator for the <code>Vertex</code> identified by
         * the input parameter.
         * 
         * @param index Identifies a <code>Vertex</code>.
         */
        public EdgeIterator(int index) 
        {
            vIndex = index;
            current = null;
        }
        
        /**
         * Tells whether there are more <code>Edge</code>s in the list.
         * 
         * @return <code>true</code> if there are more elements; otherwise
         * <code>false</code>.
         */
        @Override
        public boolean hasNext()
        {
            if (current == null){
                return adjList[vIndex].head != null;
            }
            
            return (current.successor != null);
        }
        
        /**
         * Provide the caller a handle to the next <code>Edge</code> object in 
         * the list.
         * 
         * @return Handle to an <code>Edge</code> object.
         * @precondition There are more elements in the list.
         */
        @Override
        public Edge next()
        {
            // Are there more edges in the list?
            if (!hasNext()){
                throw new RuntimeException();
            }
            
            // First time accessing an edge in the list?
            if (current == null){
                current = adjList[vIndex].head;
            }
            else {
                current = current.successor;
            }
            
            return current;
        }
     
        /**
         *  Not supported.
         *  @throws UnsupportedOperationException always.
         */
        @Override
        public void remove() 
        {
            throw new UnsupportedOperationException();
        }   
    }
    
    
    /**
     * Class for iterating through vertices in the graph.
     */
    public class VertexIterator implements Iterator
    {
        /** Index of adjacency list entry currently pointed to by 
            the iterator. */
        private int current;
        
        /**
         * Create a new iterator.
         */
        public VertexIterator ()
        {
            current = -1;
        }
        
        /**
         * Tells the caller whether there are more vertices to iterate over.
         * 
         * @return <code>true iff there are more vertices; otherwise <code>
         * false</code>.
         */
        @Override
        public boolean hasNext() 
        { 
            return (current < adjList.length - 1);
        }
        
        /**
         * Provide the caller a handle to the next vertex in the graph.  <br />
         * Note: Method provides a handle to the actual vertex, not a copy of 
         * the vertex, so care must be taken not to corrupt the data.  Future
         * implementation should provide a copy of the <code>Vertex</code>.
         * 
         * @return A handle to the next vertex in the graph.                    
         */
        @Override
        public Vertex next() 
        {
            return adjList[++current].thisVertex;
        }
        
        /**
         * Provides an <code>EdgeIterator</code> for iterating over edges 
         * incident on the <code>Vertex</code> currently pointed to by the 
         * <code>VertexIterator</code>.  <code>VertexIterator.next()</code>
         * must be called at least once before using 
         * <code>VertexIterator.getEdgeIterator()</code>.
         * 
         * @return An <code>EdgeIterator</code> pointing to the first incident
         * edge, which may be <code>NULL</code>.
         */
        public EdgeIterator getEdgeIterator ()
        {
            return new EdgeIterator( current );
        }
        
        /**
         * Unsupported operation.
         * @throws UnsupportedOperationException always.
         */
        @Override
        public void remove() 
        {
            throw new UnsupportedOperationException();
        }
    }
    
    
    /** Adjacency list representation of the graph. */
    protected AdjListEntry[] adjList;
    
    /** Default capacity of the adjacency list. */
    private final int DEFAULT_CAPACITY = 10;
    
    /** Minimum allowable capacity of the adjacency list. */
    private final int MIN_ALLOWABLE_CAPACITY = 2;
       
    /** Points the last entry in the adjacency list. */
    private int tail;
    
    
    /**
     * Instantiate an empty <code>AdjacencyListGraph</code> with the 
     * default capacity.
     */
    public AdjacencyListGraph()
    {
        adjList = new AdjListEntry[ DEFAULT_CAPACITY ];
        tail = -1;
    }
    
    
    /**
     * Instantiates an empty <code>AdjacencyListGraph</code> with given 
     * capacity.
     * 
     * @param capacity Desired capacity of the adjacency list. Must be >= 2.
     * @throws IllegalArgumentException if parameter is < 2.
     */
    public AdjacencyListGraph(int capacity) throws IllegalArgumentException
    {
        // Invalid capacity?
        if (capacity < MIN_ALLOWABLE_CAPACITY) {
            throw new IllegalArgumentException();
        }
        
        adjList = new AdjListEntry[ capacity ];
        tail = -1;
    }
    
    
    /**
     * Add a <code>Vertex</code> to the graph, and set the <code>Vertex</code>
     * identifier equal to the its position in the adjacency list.
     * 
     * @param v <code>Vertex</code> to add to graph.
     */
    @Override
    public void addVertex(Vertex v)
    {
        adjList[++tail] = new AdjListEntry(v);
        adjList[tail].thisVertex.setIdentifier(tail);
    }
    
    
    /**
     * Adds a directed edge between the given vertices.
     * 
     * @param u A   <code>Vertex</code> in the adjacency list.
     * @param v     The <code>Vertex</code> adjacent to <code>Vertex u</code>.
     */
    @Override
    public void addEdge(Vertex u, Vertex v) 
    {
        // Store the index for code readability.
        int uIndex = u.getIdentifier();
        
        // Create the new edge.
        Edge edge = new Edge(v, adjList[uIndex].head);
        
        // Add the edge to the adjacency list.
        adjList[uIndex].head = edge;
    }
    
    
    /**
     * Adds a directed edge between the vertices at the given indices. 
     * 
     * @param uIndex    Index of a <code>Vertex</code>.
     * @param vIndex    Index of a <code>Vertex</code>.
     */
    public void addEdge(int uIndex, int vIndex)
    {
        addEdge( adjList[uIndex].thisVertex, adjList[vIndex].thisVertex);
    }
    
    
    /**
     * Provides a handle to the <code>Vertex</code> at the given index.
     * 
     * @param index     Index of a <code>Vertex</code> in the adjacency list. 
     * @return          Handle to a <code>Vertex</code> object.
     * @throws IndexOutOfBoundsException if index is not in adjacency list.
     */
    @Override
    public Vertex getVertex(int index) throws IndexOutOfBoundsException
    {
        // Valid index?
        if (index < 0 || index > adjList.length - 1) {
            throw new IndexOutOfBoundsException();
        }
        
        return adjList[index].thisVertex;
    }
    
    
    /**
     * Tells the size of the adjacency list.  If the graph has been fully
     * built, this value is the same as the number of vertices in the
     * graph.
     * 
     * @return Size of the adjacency list.
     */
    public int getCapacity () 
    {
        return adjList.length;
    }
    
    
    /**
     * Provides a string representation of the graph in adjacency list form.
     * Output is for the form:
     *  [VertexId]( IncidentEdgeId_1  IncidentEdgeId_2 ... )
     * 
     * @return  String representation of the graph.
     */ 
    @Override
    public String toString()
    {
        String str = "";
        
        VertexIterator vitr = new VertexIterator();
        
        while (vitr.hasNext())
        {
             // Print AdjListEntry.Vector
            Vertex u = vitr.next();
            str += "[" + u.getIdentifier() + "]( ";
            
            // Print all the edges
            EdgeIterator eitr = vitr.getEdgeIterator();
            while (eitr.hasNext())
            {
                Edge e = eitr.next();
                str += e.vert.getIdentifier() + " ";
            }
            
            str += ")\n";
        }

        System.out.println(str);
        return str;
    }
}
